我要招人

去企业版

首页 > 试题广场 >

二叉搜索树的第k个节点

[编程题]二叉搜索树的第k个节点

热度指数：54923 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一棵结点数为n 二叉搜索树，请找出其中的第 k 小的TreeNode结点值。

1.返回第k小的节点值即可

2.不能查找的情况，如二叉树为空，则返回-1，或者k大于n等等，也返回-1

3.保证n个节点的值不一样

数据范围： $0 \le n \le1000$ ， $0 \le k \le1000$ ，树上每个结点的值满足 $0 \le val \le 1000$
进阶：空间复杂度 $O(n)$ ，时间复杂度 $O(n)$

如输入{5,3,7,2,4,6,8},3时，二叉树{5,3,7,2,4,6,8}如下图所示：

该二叉树所有节点按结点值升序排列后可得[2,3,4,5,6,7,8]，所以第3个结点的结点值为4，故返回对应结点值为4的结点即可。

示例1

输入

{5,3,7,2,4,6,8},3

输出

示例2

输入

{},1

输出

-1

备注:

当树是空

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

查看答案及解析

Python 3

来牛客玩玩

class Solution:
    def visitNode(self, res, proot):
        if not proot:
            return
        self.visitNode(res, proot.left)
        res.append(proot.val)
        self.visitNode(res, proot.right)
        return res
    
    def KthNode(self , proot: TreeNode, k: int) -> int:
        # write code here
        if not proot&nbs***bsp;k == 0:
            return -1
        res = self.visitNode([], proot)
        return self.visitNode([], proot)[k-1] if len(res) >= k else -1

发表于 2022-08-14 15:30:45 回复(0)

Python 3

Vivimore

class Solution:
    res = []
    n = 0
    def dfs(self, proot):
        if not proot:
            return 
        self.dfs(proot.left)
        self.n += 1
        self.res.append(proot.val)
        self.dfs(proot.right)

    def KthNode(self , proot: TreeNode, k: int) -> int:
        self.dfs(proot)
        if not proot or k == 0 or k > self.n:
            return -1
        return self.res[k-1]

发表于 2022-05-09 20:52:35 回复(0)

Python 3

kinter1

class Solution:
    def __init__(self):
        self.n = 0
    def KthNode(self , proot: TreeNode, k: int) -> int:
        if proot is None:
            return -1
        left_data = self.KthNode(proot.left, k)
        if left_data != -1:
            return left_data
        self.n += 1
        if k == self.n:
            return proot.val
        right_data = self.KthNode(proot.right, k)
        return right_data

python递归解法

发表于 2022-02-25 14:02:23 回复(0)

Python 3

牛客787860663号

中序遍历？交换下树里叶节点的位置不就错了吗？

发表于 2022-01-21 11:12:35 回复(0)

Python 3

Joy_9

class Solution:
    def KthNode(self , proot: TreeNode, k: int) -> int:
        # write code here
        if not proot&nbs***bsp;k==0:
            return -1
        res=[]
        def inorder(root):
            if not root:
                return
            inorder(root.left)
            res.append(root.val)
            inorder(root.right)
        inorder(proot)
        return res[k-1] if k<=len(res) else -1

发表于 2022-01-17 08:32:17 回复(0)

Python 3

讯飞内推官

class Solution:
def __init__(self):
self.idx = 0
def tra(self , proot: TreeNode, k: int) -> int:
# write code here
if not proot or k<1:
return -1
l = self.KthNode(proot.left, k)
self.idx += 1
if self.idx==k:
return proot.val
r = self.KthNode(proot.right, k)
if l and l > 0:
return l
if r and r > 0:
return r
def KthNode(self , proot: TreeNode, k: int) -> int:
if not proot or k<1:
return -1
ret = self.tra(proot,k)
if self.idx<k:
return -1
return ret

发表于 2022-01-04 14:55:07 回复(0)

Python 3

ZzBobobo

class Solution:

def KthNode(self , proot: TreeNode, k: int) -> int:

#判断树和k是否符合标准

if proot == None or k == 0:

return -1

#中序遍历

        def sort(proot) ->list:
            l = []
            r = []
            if proot.left:
                l += sort(proot.left)
            m = [proot.val]
            if proot.right:
                r += sort(proot.right)

return l + m + r

#最后判断k是否大于树的节点数

        if len(sort(proot)) < k:
            return -1
        return sort(proot)[k-1]

发表于 2021-11-27 16:52:20 回复(0)

Python 3

勇敢牛牛，不怕困难！

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param proot TreeNode类 
# @param k int整型 
# @return int整型
#
class Solution:
    def KthNode(self , proot: TreeNode, k: int) -> int:
        # corner case
        if not proot: return -1

        stk, trav = [], proot
        while stk&nbs***bsp;trav:
            while trav:
                stk.append(trav)
                trav = trav.left
                
            k -= 1
            if not k: return stk[-1].val
        
            trav = stk[-1].right
            stk.pop()
            
        return -1

发表于 2021-11-24 10:41:02 回复(1)

Python 3

阿司匹林Yo

class Solution:
    # 中序遍历
    def midtravel(self, root, list):
        if not root:
            return
        self.midtravel(root.left, list)
        list.append(root.val)
        self.midtravel(root.right, list)

    def KthNode(self, proot: TreeNode, k: int) -> int:
        if not proot&nbs***bsp;k <= 0:
            return -1
        nodes = []
        self.midtravel(proot, nodes)
        return nodes[k-1] if k <= len(nodes) else -1

发表于 2021-11-20 16:40:55 回复(0)